// 快排的核心思想是：分治
// 需要思考两个问题 1.为什么右边先走 2.为什么相遇点总是小于keyi
// 需要进行两次优化 1.三数取中 2.小区间优化
void QuickSort1(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if (right - left + 1 < 10)
	{
		InsertSort(arr + left, right - left + 1);	//注意这里插入排序的起始地址
		return;
	}
	int mid = GetMiddle(arr, left, right);
	Swap(&arr[mid], &arr[left]);
	int keyi = left;
	int begin = left, end = right;
	while (begin < end)
	{
		// 右边先走
		while ((begin < end) && (arr[end] >= arr[keyi]))
		{
			end--;
		}
		while ((begin < end) && (arr[begin] <= arr[keyi]))
		{
			begin++;
		}
		Swap(&arr[begin], &arr[end]);
	}
	Swap(&arr[keyi], &arr[begin]);
	keyi = begin;
	// [left, keyi - 1] keyi [keyi + 1, right]
	QuickSort1(arr, left, keyi - 1);
	QuickSort1(arr, keyi + 1, right);
}

void QuickSort2(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if (right - left + 1 < 10)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}
	int mid = GetMiddle(arr, left, right);
	Swap(&arr[mid], &arr[left]);
	int keyi = left;
	int key = arr[left];
	int begin = left, end = right;
	while (begin < end)
	{
		while ((begin < end) && (arr[end] >= key))
		{
			end--;
		}
		arr[keyi] = arr[end];
		keyi = end;
		while ((begin < end) && (arr[begin] <= key))
		{
			begin++;
		}
		arr[keyi] = arr[begin];
		keyi = begin;
	}
	arr[keyi] = key;
	QuickSort2(arr, left, keyi - 1);
	QuickSort2(arr, keyi + 1, right);
}

void QuickSort3(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if (right - left + 1 < 10)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}
	int mid = GetMiddle(arr, left, right);
	int keyi = left;
	Swap(&arr[mid], &arr[left]);
	int prev = left, cur = left + 1;
	while (cur <= right)
	{
		if ((arr[cur] < arr[keyi]) && (++prev != cur))
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[keyi], &arr[prev]);
	keyi = prev;
	// [left, keyi - 1] keyi [keyi + 1, right] 
	QuickSort3(arr, left, keyi - 1);
	QuickSort3(arr, keyi + 1, right);
}

void QuickSort4(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	if (right - left + 1 < 10)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}
	int begin = left, end = right;
	int mid = GetMiddle(arr, left, right);
	int keyi = left;
	Swap(&arr[mid], &arr[left]);
	int cur = left + 1;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi])
		{
			Swap(&arr[cur], &arr[keyi]);
			left++;
			cur++;
		}
		else if (arr[cur] > arr[keyi])
		{
			Swap(&arr[cur], &arr[right]);
			right--;
		}
		else
		{
			cur++;
		}
	}
	// [begin, left - 1] keyi [right + 1, end] 
	QuickSort3(arr, begin, left - 1);
	QuickSort3(arr, right + 1, end);
}

void QuickSortR1(int* arr, int left, int right)
{
	ST s;
	STInit(&s);
	// 注意是先入右，再入左。出的时候就是先左后右了。
	STPush(&s, right);
	STPush(&s, left);
	while (!STEmpty(&s))
	{
		int begin = STTop(&s);
		STPop(&s);
		int end = STTop(&s);
		STPop(&s);

		// 以下是双指针的过程
		int mid = GetMiddle(arr, begin, end);
		int keyi = begin;
		Swap(&arr[mid], &arr[begin]);
		int prev = begin, cur = begin + 1;
		while (cur <= end)
		{
			if ((arr[cur] < arr[keyi]) && (++prev != cur))
			{
				Swap(&arr[prev], &arr[cur]);
			}
			cur++;
		}
		Swap(&arr[keyi], &arr[prev]);
		keyi = prev;

		// [begin, keyi - 1] keyi [keyi + 1, end]
		if (keyi + 1 < end)
		{
			STPush(&s, end);
			STPush(&s, keyi + 1);
		}
		if (begin < keyi - 1)
		{
			STPush(&s, keyi - 1);
			STPush(&s, begin);
		}
	}
	STDestroy(&s);
}

void QuicKSortR2(int* arr, int left, int right)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, left);
	QueuePush(&q, right);
	while (!QueueEmpty(&q))
	{
		int begin = QueueFront(&q);
		QueuePop(&q);
		int end = QueueFront(&q);
		QueuePop(&q);

		// 以下是双指针的过程
		int mid = GetMiddle(arr, begin, end);
		int keyi = begin;
		Swap(&arr[begin], &arr[mid]);
		int prev = begin, cur = begin + 1;
		while (cur <= end)
		{
			if ((arr[cur] < arr[keyi]) && (++prev != cur))
			{
				Swap(&arr[prev], &arr[cur]);
			}
			cur++;
		}
		Swap(&arr[keyi], &arr[prev]);
		keyi = prev;

		// [begin, keyi - 1] keyi [keyi + 1, end]
		if (begin < keyi - 1)
		{
			QueuePush(&q, begin);
			QueuePush(&q, keyi - 1);
		}
		if (keyi + 1 < end)
		{
			QueuePush(&q, keyi + 1);
			QueuePush(&q, end);
		}
	}
	QueueDestroy(&q);
}
